import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Heap {
    public int[] elem;
    public int usedSize;

    public Heap() {
        this.elem = new int[10];
    }
    //创建堆
    public void createHeap(int[] array){
        //准备数据
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            usedSize++;
        }
        //建堆
        for (int p = (usedSize-1-1)/2; p >=0; p--) {
            shiftDown(p,usedSize);
        }
    }
    //root 为每棵子树的根节点下标
    //len 为每棵子树调整结束的结束条件
    //大根堆向下调整法
    public void shiftDown(int root,int len) {
        int parent=root;
        int child=parent*2+1;
        while(child<len){
            //如果有左孩子和右孩子比较左右孩子大小，使child指向大的
            if(child+1<len && elem[child]<elem[child+1]){
                child++;
            }
            //判断是否是大根堆
            if(elem[child]>elem[parent]){
                int temp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=temp;
                //判断完根节点后向下判断整棵树是否都为大根堆
                parent=child;
                child=parent*2+1;
            }else{
                break;//说明是大根堆，不在判断
            }
        }
    }
    //插入
    public void push(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        //把添加的数据放在堆最后
        elem[usedSize]=val;
        //向上调整为大根堆
        shiftUp(usedSize);
        //有效元素下标加1
        usedSize++;
    }
    //向上调整
    private void shiftUp(int child){
       int parent=(child-1)/2;
       while(child>0){
           if(elem[child]>elem[parent]){
               int temp=elem[parent];
               elem[parent]=elem[child];
               elem[child]=temp;
               child=parent;
               parent=(child-1)/2;
           }else{
               break;
           }
       }
    }
    //判断堆是否满
    public boolean isFull(){
        return usedSize==elem.length;
    }
    //删除
    public void pollHeap(){
        if(isEmpty()){
            return;
        }
        int temp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=temp;
        usedSize--;
        shiftDown(0,usedSize);
    }
    //判断是否为空
    public boolean isEmpty(){
        return usedSize==0;
    }
    //获得堆顶元素
    public int peek(){
        return elem[0];
    }
    //最小的k个元素
    public int[] smallestK(int[] arr, int k) {
        int[] ret=new int[k];
        if(k<=0){
            return ret;
        }
        //大根堆
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer num1,Integer num2){
                return num2-num1;
            }
        });
        //放入前k个元素
        for(int i =0;i<k;i++){
            maxHeap.offer(arr[i]);
        }
        //判断大根堆堆顶元素是否大于剩余未入堆的元素，使堆中元素为最小的k个
        for(int i =k;i<arr.length;i++){
            if(maxHeap.peek()>arr[i]){
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        //将堆中元素放到数组中
        for(int i =0;i<k;i++){
            ret[i]=maxHeap.poll();
        }
        return ret;
    }
    //堆排序
    public void heapSort(){
        int end = usedSize-1;
        while(end>0){
            int temp=elem[0];
            elem[0]=elem[end];
            elem[end]=temp;
            shiftDown(0,end);
            end--;
        }
    }
}
